package com.lft.tree06.huffman_tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈夫曼树
 */
public class HuffmanTree {
	public static void main(String[] args) {
		int[] a = {13, 7, 8, 3, 29, 6, 1};
		Node node = createHuffmanTree(a);
		preOrder(node);
	}
	
	/**
	 * 创建哈夫曼树的方法
	 * @param a 原始数组
	 * @return
	 */
	public static Node createHuffmanTree(int[] a) {
		// 第一步，为了操作方便。
		// 1. 遍历 a 数组
		// 2. 将 a 的每个元素构成一个 Node
		// 3. 将 Node 放入到 ArrayList中
		List<Node> nodes = new ArrayList<>();
		for (int value : a) {
			nodes.add(new Node(value));
		}
		while (nodes.size() > 1) {
			// 排序
			Collections.sort(nodes);
			// 取出根节点权值最小的两颗二叉树
			// （1）取出权值最小的节点（二叉树）
			Node leftNode = nodes.get(0);
			// （2）取出权值次小的节点（二叉树）
			Node rightNode = nodes.get(1);
			// （3）构建一个新的二叉树
			Node parent = new Node(leftNode.getValue() + rightNode.getValue());
			parent.setLeft(leftNode);
			parent.setRight(rightNode);
			// （4）从ArrayList中删除处理过的二叉树
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parent);
		}
		return nodes.get(0);
	}
	
	/**
	 * 前序遍历
	 */
	public static void preOrder(Node root) {
		if (root != null) {
			root.preOrder();
		} else {
			System.out.println("是空树，不能遍历~~");
		}
	}
}

/**
 * 节点类
 * 为了让 Node 对象支持排序，例如 Collections 集合排序。
 * 让 Node 类 实现 Comparable接口。
 */
class Node implements Comparable<Node> {
	/**
	 * 节点权值
	 */
	private int value;
	/**
	 * 指向左子节点
	 */
	private Node left;
	/**
	 * 指向右子节点
	 */
	private Node right;
	
	public Node(int value) {
		this.value = value;
	}
	
	public void preOrder() {
		System.out.println(this.getValue());
		if (this.getLeft() != null) {
			this.getLeft().preOrder();
		}
		if (this.getRight() != null) {
			this.getRight().preOrder();
		}
	}
	
	public int getValue() {
		return value;
	}
	
	public void setValue(int value) {
		this.value = value;
	}
	
	public Node getLeft() {
		return left;
	}
	
	public void setLeft(Node left) {
		this.left = left;
	}
	
	public Node getRight() {
		return right;
	}
	
	public void setRight(Node right) {
		this.right = right;
	}
	
	@Override
	public String toString() {
		return "Node{" +
				"value=" + value +
				'}';
	}
	
	@Override
	public int compareTo(Node o) {
		// 从小到大排序
		return this.getValue() - o.getValue();
		
		// // 从大到小排序
		// return o.getValue() - this.getValue();
	}
	
}